An important function of any modern digital communications system is error control coding. Error control coding is the field of communications that deals with techniques for detecting and correcting errors in a digital system. Generally, error detecting/correcting schemes are utilized whenever it is desired to ensure that, during transmission or through storage of digital data, error is not introduced into the data, or in the alternative, if error is introduced into the data, that the introduced error is corrected. The ability to detect and/or correct data errors is accomplished by adding redundancy to the data. The inclusion of redundant bits in transmitted or stored data results in a coded signal or field comprised of more bits than the original uncoded signal or field.
One frequently used scheme for error detection/correction is through the use of so-called Reed-Solomon codes. Reed-Solomon codes are non-binary systematic cyclic linear block codes. Non-binary codes work with symbols that are comprised of several bits. Non-binary code, such as the Reed-Solomon code, are good at correcting burst errors because the correction by these codes is done on the symbol level. A systematic code, such as the Reed-Solomon code, generates codewords that contain the message symbols in unaltered form. The encoder applies a reversible mathematical function to the message symbols in order to generate the redundancy, or parity, symbols. The codeword is then formed by appending the parity symbols to the message symbols. The Reed-Solomon code is considered a cyclical code because a circular shift of any valid codeword also produces another valid codeword. Cyclic codes are popular because there exist efficient and inexpensive decoding techniques to implement them. Finally, the Reed-Solomon code is considered linear because the addition of any two valid codewords results in another valid codeword.
A typical Reed-Solomon decoder is comprised of the following major component blocks: (i) a syndrome generating block, (ii) an error polynomial block, (iii) an error location block, and (iv) an error magnitude block, (v) an error correcting block, and (vi) a delay block. The syndrome generating block is used to receive a codeword and generate a syndrome from the codeword. The syndrome is utilized to create an error polynomial in the error polynomial block. The error polynomial is passed onto the error location and error magnitude blocks, in which error locations and magnitudes for a codeword are respectively determined. An error vector is generated from the error location and magnitude. A delayed version of the received codeword is corrected by the error correcting block using the error vector corresponding to a specific codeword. The delay block is comprised of a memory to store the received codeword while the decoding process is performed to produce the error vector.
Prior art decoders use these blocks to form a “delivery pipeline.” That is, the input to one block only depends on the output of a previous block and there is no feedback from one component block to a previous or subsequent block. Therefore, only one codeword at a time may be processed, and the next codeword to be processed isn't begun until the processing of the previous codeword is completed.